Large scale parallel computing systems comprise a large number of Processing Elements (PEs) which communicate via an interconnect system. The performance of these computing systems is influenced by both the performance of the interconnect and the performance and number of the interconnected PEs. An individual PE consists of one or more processors, memory, inter-connect interfaces, and may be physically implemented as a chip, board, or collection of boards, blade, rack, or a cluster of racks. Optionally, a PE may also contain secondary disk storage, and additional Input-Output (I/O) interfaces to additional general-purpose networks.
The interconnect system consists of a set of routers or switches connected by electrical or optical links. Each link connects a router to another router or to a PE which is viewed as a terminal node of the interconnect system. Terminal nodes are sources or destinations for communication packets and routers are responsible for successfully routing packets from source to destination PEs. The performance of the interconnect system depends on three components: the topology, the switch, and the routing algorithm that is implemented in the switch. Many routing algorithms are dependent upon the topology choice, and most switch architectures are dependent on both the topology and the routing algorithm choices.
Numerous topologies and routing algorithms have been proposed in the literature. Example topologies are two dimensional (2D) or three dimensional (3D) meshes, crossbars, multi-stage networks (e.g., the butterfly, banyan, or Benes networks), Clos, folded-Clos, and flattened butterfly.
Routing algorithms can be classified into three classes. Deterministic routers choose a fixed route between any source-destination pair. Oblivious routers choose paths dynamically, but the choice is not based on network load. Adaptive routers choose a path based on network load in an attempt to improve performance by dynamically avoiding congested links or switches.
Additional important routing considerations are deadlock avoidance, minimizing path lengths or hops, and whether or not packets from a single source are delivered to the destination in the order in which they were sent. Adaptive routing algorithms inherently do not guarantee in-order packet delivery and hence an additional burden is placed on the destination PE to reorder packets based on packet sequence tags that are contained in the packet.